#include "bnb.h"


/* Constroi o vetor com a permutacao dada pela indexacao dos jobs */
int* setPerm(const int *index, const int n, const int nJobs) {
    int *perm;
    int i, k;

    perm = (int*)memAlloc(sizeof(int) * nJobs);

    k = 0;

    for (i = 0; i < nJobs; i++) {
        if (index[i] >= 0) {
            perm[index[i]] = i;
        } else {
            perm[n+k] = i;
            k++;
        }
    }

    return perm;
}


/* Funcao que imprime o conteudo de um no */
void printNode(const Node *nd, const int nJobs) {
    int i, n, *perm;

    n = nd->nSched;
    perm = setPerm(nd->sched, n, nJobs);

    fprintf(stderr, "Node->id: %d\n", nd->id);
    fprintf(stderr, "Node->acc1: %d // Node->acc2: %d\n", nd->acc1, nd->acc2);
    fprintf(stderr, "Node->sft: %d // Node->lowBound: %d\n", nd->sft, nd->lowBound);
    fprintf(stderr, "Node->nSched: %d\n", nd->nSched);
    fprintf(stderr, "Node->sched: ");
    for (i = 0; i < nJobs; i++) {
        fprintf(stderr, "%d ", nd->sched[i]);
    }
    fprintf(stderr, "\nNode perm: ");
    for (i = 0; i < n; i++) {
        fprintf(stderr, "%d ", perm[i]+1);
    }
    fprintf(stderr, "\n\n");

    free(perm);
}


/* Imprime a fila de prioridade */
void printQueue(const Node **queue, const int qSize, const int nJobs) {
    int i;
    
    fprintf(stderr, "** imprimindo fila\n");
    for (i = 1; i <= qSize; i++) {
        fprintf(stderr, "> posicao %d\n", i);
        printNode(queue[i], nJobs);
    }
    fprintf(stderr, "** fim fila\n\n");
}


/* Libera a memoria de um no */
void freeNode(Node *nd) {
    free(nd->sched);
    free(nd);
}


/* Calcula o lower bound do no */
int calcLowBound(const Node *nd, const Job *jobs,
        const Job *jobsSortT1, const Job *jobsSortT2, const int nJobs) {
    
    int i, s1, s2, k1, k2, mint1ns;

    s1 = 0;
    s2 = 0;
    k1 = nd->nSched + 1;
    k2 = nd->nSched + 1;
    mint1ns = INT_MAX;

    for (i = 0; i < nJobs; i++) {
        
        if (nd->sched[ jobsSortT1[i].id ] < 0) {
            s1 += (nJobs - k1 + 1)*jobsSortT1[i].task1 + jobsSortT1[i].task2;
            k1++;
        }

        if (nd->sched[ jobsSortT2[i].id ] < 0) {
            s2 += (nJobs - k2 + 1)* jobsSortT2[i].task2;
            k2++;
        }

        if ((nd->sched[i] < 0) && (jobs[i].task1 < mint1ns)){
            mint1ns = jobs[i].task1;
        }
    }

    s1 += (nJobs - nd->nSched) * nd->acc1;
    s2 += (nJobs - nd->nSched) * max(nd->acc2, nd->acc1 + mint1ns);

    return (nd->sft + max(s1, s2));
}


/* Cria o primeiro no do conjunto (problema original) */
Node* generateFirstNode(const Job *jobs, const int nJobs) {
    int i;
    Node *nd;
   
    /* cria o no inicial e seus respectivos valores */
    nd = (Node*)memAlloc(sizeof(Node));
    nd->id = 0;
    nd->acc1 = 0;
    nd->acc2 = 0;
    nd->nSched = 0;
    nd->lowBound = -1;
    nd->sft = 0;
    nd->sched = (int*)memAlloc(sizeof(int)*nJobs);

    for (i = 0; i < nJobs; i++) {
        nd->sched[i] = -1;
    }

    return nd;
}


/* Determina a solucao padrao */
Node* generateDefaultSolution(const Job *jobs, const int nJobs) {
    int i;
    Node *sol;

    sol = generateFirstNode(jobs, nJobs);
    sol->id = -1;

    for (i = 0; i < nJobs; i++) {
        sol->sched[i] = i;
        sol->acc1 += jobs[i].task1;
        sol->acc2 = max(sol->acc2, sol->acc1) + jobs[i].task2;
        sol->sft += sol->acc2;
    }

    sol->lowBound = sol->sft;

    return sol;
}


/* Gera um filho incluindo o job dado no fim */
Node* generateChild(const Node *parent, const int nextJob, const int id, const int nJobs,
        const Job *jobs, const Job *jobsSortT1, const Job *jobsSortT2) {

    Node *child;
    int i;

    child = (Node*)memAlloc(sizeof(Node));
    child->sched = (int*)memAlloc(sizeof(int)*nJobs);
    child->nSched = parent->nSched + 1;
    child->id = id;

    /* copia o vetor de schedule */
    for (i = 0; i < nJobs; i++) {
        child->sched[i] = parent->sched[i];
    }
    child->sched[nextJob] = parent->nSched;

    /* calcula os valores definidos pela permutacao */
    child->acc1 = parent->acc1 + jobs[nextJob].task1;
    child->acc2 = max(parent->acc2, child->acc1) + jobs[nextJob].task2;
    child->sft = parent->sft + child->acc2;
    child->lowBound = calcLowBound(child, jobs, jobsSortT1, jobsSortT2, nJobs);

    return child;
}


/* Funcao que verifica se duas schedules contem os mesmos jobs */
int sameSched(const int *a, const int *b, const int nJobs) {
    int i, iguais;

    iguais = 1;
    i = 0;

    while ((i < nJobs) && (iguais)) {
        if ( ((a[i] >= 0) && (b[i] <  0)) ||
             ((a[i] <  0) && (b[i] >= 0)) ) {
            
            iguais = 0;
        }
        i++;
    }

    return iguais;
}


/* Funcao que verifica a dominancia de um dado node */
int verificaDominante(const Node *nd, Node **actvNodes, int *nActvNodes, const int nJobs) {
    int i, dominado; 
    Node *aux;

    dominado = 0;

    for (i = 1; i <= *nActvNodes; i++) {

        if ((nd->nSched == actvNodes[i]->nSched) &&
                (nd->acc2 <= actvNodes[i]->acc2) &&
                (nd->sft <= actvNodes[i]->sft) &&
                (sameSched(nd->sched, actvNodes[i]->sched, nJobs))) {
        
            /* nd domina actvNodes[i] */
            aux = queueRemove(actvNodes, nActvNodes, i);

            if (DEBUG) {
                fprintf(stderr, "** no sendo removido devido a dominancia: \n");
                printNode(aux, nJobs);
            }

            freeNode(aux);
            i--;
        
        } else if ((nd->nSched == actvNodes[i]->nSched) && 
                (nd->acc2 >= actvNodes[i]->acc2) &&
                (nd->sft >= actvNodes[i]->sft) &&
                (sameSched(nd->sched, actvNodes[i]->sched, nJobs))) {
        
            /* nd eh dominado por actvNodes[i] */
            if (DEBUG) {
                fprintf(stderr, "** no sera removido pois eh dominado por: \n");
                printNode(actvNodes[i], nJobs);
            }

            dominado++;
        }
    }

    return (dominado > 0);
}


/* Verifica a melhor solucao encontrada */
void buildAnswer(Solution *ans, Node *bestSol, Node *branchNode,
        const Job *jobs, const int nJobs, const int maxExecTime) {
    int i, min, valormin;
    struct itimerval timer;


    if (branchNode == NULL) {
        ans->ndSol = bestSol;
        return;
    }

    /* -- finaliza o branchnode com a heuristica 1 -- */
    /* para cada job nao scheduled */
    while (branchNode->nSched < nJobs) {
        
        valormin = INT_MAX;

        /* encontra o menor task1+task2 nao scheduled */
        for (i = 0; i < nJobs; i++) {
            if ((branchNode->sched[i] < 0) && (valormin > jobs[i].task1 + jobs[i].task2)) {
                valormin = jobs[i].task1 + jobs[i].task2;
                min = i;
            }
        }

        /* escalona min */
        branchNode->sched[min] = branchNode->nSched;
        branchNode->acc1 += jobs[min].task1;
        branchNode->acc2 = max(branchNode->acc2, branchNode->acc1) + jobs[min].task2;
        branchNode->sft += branchNode->acc2;
        branchNode->nSched++;
    }

    branchNode->lowBound = branchNode->sft;


    /* verifica o melhor */
    if (bestSol->lowBound < branchNode->lowBound) {
        ans->ndSol = bestSol;
        freeNode(branchNode);
    } else {
        ans->ndSol = branchNode;
        ans->primalv = branchNode->lowBound;
        getitimer(ITIMER_REAL, &timer);
        ans->primalt = maxExecTime - timer.it_value.tv_sec;
        freeNode(bestSol);
    }
}


/* Funcao que resolve o FSP por BnB */
Solution* bnb(const Job *jobs, const int nJobs, const int maxExecTime, const int maxNodes) {
    Solution *ans;
    int nActvNodes, actvNodesSize, msgTime, tmp;
    int upBound, nNodesChecked, i, id;
    Node **actvNodes, *branchNode, *newNode;
    Node *bestSol, *oldBestSol;
    Job *jobsSortT1, *jobsSortT2;
    struct itimerval timer;


    /* gera os vetores ordenados por task1 e task2 */
    jobsSortT1 = (Job*)memAlloc(sizeof(Job)*nJobs);
    jobsSortT2 = (Job*)memAlloc(sizeof(Job)*nJobs);

    for (i = 0; i < nJobs; i++) {
        jobsSortT1[i] = jobs[i];
        jobsSortT2[i] = jobs[i];
    }

    qsort(jobsSortT1, nJobs, sizeof(Job), (int(*)(const void*, const void*))nodeTask1cmp);
    qsort(jobsSortT2, nJobs, sizeof(Job), (int(*)(const void*, const void*))nodeTask2cmp);

    /* controle de tempo de execucao */
    setTimer(maxExecTime);
    getitimer(ITIMER_REAL, &timer);

    /* inicializacao de variaveis */
    ans = (Solution*)memAlloc(sizeof(Solution));
    ans->primalt = 1;
    ans->dualt = 1;

    bestSol = generateDefaultSolution(jobs, nJobs);

    actvNodesSize = ACTV_NODES_SIZE;
    actvNodes = (Node**)memAlloc(sizeof(Node*) * actvNodesSize);

    actvNodes[1] = generateFirstNode(jobs, nJobs);
    nActvNodes = 1;
    nNodesChecked = 0;
    upBound = bestSol->lowBound;
    ans->primalv = upBound;
    ans->dualv = actvNodes[1]->lowBound;
    id = 1;
    msgTime = TIMER_MSG;


    /* enquanto houver nos ativos */
    while ((nActvNodes > 0) && (nNodesChecked < maxNodes) && (timer.it_value.tv_sec > 0)) {

//        if (DEBUG) printQueue(actvNodes, nActvNodes, nJobs);

        /* pega o no ativo com menor lower bound */
        branchNode = queueRemove(actvNodes, &nActvNodes, 1);
        tmp = branchNode->lowBound;

        if (DEBUG) {
            fprintf(stderr, "** no removido da lista!\n");
            printNode(branchNode, nJobs);
        }

        /* explorando o no removido */
        if (branchNode->lowBound >= upBound) {

            /* lower bound nao menor que o upper bound */
            if (DEBUG) fprintf(stderr, "** excluindo o no!\n\n");
            freeNode(branchNode);

        } else if (branchNode->nSched == nJobs) {

            /* solucao melhor encontrada */
            if (DEBUG) fprintf(stderr, "** no eh best solution!\n\n");
            upBound = branchNode->lowBound;
            oldBestSol = bestSol;
            bestSol = branchNode;
            freeNode(oldBestSol);

            /* atualizar valor primal (solucao melhor encontrada) */
            ans->primalv = upBound;
            getitimer(ITIMER_REAL, &timer);
            ans->primalt = maxExecTime - timer.it_value.tv_sec;

        } else {
            
            /* verifica se vale a pena explorar o no */
            if (! verificaDominante(branchNode, actvNodes, &nActvNodes, nJobs)) {

                /* para cada job ainda a ser scheduled */
                for (i = 0; i < nJobs; i++) {
                    if (branchNode->sched[i] < 0) {
                        /* gera um no filho escolhendo o job i */
                        newNode = generateChild(branchNode, i, id++, nJobs, jobs, jobsSortT1, jobsSortT2);

                        /* DEBUG: imprime o no gerado */
                        if (DEBUG) {
                            fprintf(stderr, "** novo no gerado e inserido na arvore para ramificacao!\n");
                            printNode(newNode, nJobs);
                        }
                
                        if (nActvNodes == actvNodesSize-1) {
                            actvNodesSize = actvNodesSize * 2;
                            actvNodes = (Node**)realloc(actvNodes, sizeof(Node*) * actvNodesSize);
                            if (actvNodes == NULL) {
                                perror("realloc");
                                exit(EXIT_FAILURE);
                            }
                        }
                        queueInsert(actvNodes, &nActvNodes, newNode);
                    }
                }
            }
       

            freeNode(branchNode);
    
        }

        /* atualizar valor dual (novo no ativo) */
        if ((ans->dualv <= tmp) && (tmp < upBound) &&
                (nActvNodes > 0) && (actvNodes[1]->lowBound > tmp)) {
/*printf("alterando dual..\nantigo: %d ; novo: %d ; (id:%d)\nsched: ", ans->dualv, actvNodes[1]->lowBound, actvNodes[1]->id);            
for (i = 0; i < nJobs; i++) {
    printf("%d ",actvNodes[1]->sched[i]);
}
printf("\nsft: %d ; s1: %d ; s2: %d\nupbound:%d\n\n", actvNodes[1]->sft, actvNodes[1]->acc1, actvNodes[1]->acc2, upBound);*/
            ans->dualv = actvNodes[1]->lowBound;
            getitimer(ITIMER_REAL, &timer);
            ans->dualt = maxExecTime - timer.it_value.tv_sec;
        }


        /* imprime uma mensagem a cada 60s */
        if (maxExecTime - timer.it_value.tv_sec > msgTime) {
            printf("+ tempo: %d\t (%d; %d)\t %d\n",
                        msgTime, nActvNodes, nNodesChecked, upBound);
            msgTime += TIMER_MSG;
        }

        nNodesChecked++;
        getitimer(ITIMER_REAL, &timer);
    }


    /* constroi a resposta */
    if (nActvNodes > 0) {
        branchNode = queueRemove(actvNodes, &nActvNodes, 1);
    } else {
        branchNode = NULL;
    }

    buildAnswer(ans, bestSol, branchNode, jobs, nJobs, maxExecTime);

    ans->nNodesChecked = nNodesChecked + (branchNode != NULL);
    ans->timeElapsed = maxExecTime - timer.it_value.tv_sec;


    /* libera a memoria */
    for (i = 1; i <= nActvNodes; i++) {
        freeNode(actvNodes[i]);
    }
    free(actvNodes);
    free(jobsSortT1);
    free(jobsSortT2);

    return ans;
}


/* Funcao principal */
int main(int argc, const char *argv[]) {

    int maxExecTime, maxNodes;
    FILE *param, *inst;
    Job *jobs;
    Solution *solution;
    int nJobs, i, *permSol;


    /* verifica o uso */
    if (argc != 2) {
        fprintf(stderr, "uso: bnb arq_instancia\n");
        exit(EXIT_FAILURE);
    }

    /* le o arquivo param */
    param = fopen(PARAM_PATH, "r");
    fscanf(param, "%d %d", &maxNodes, &maxExecTime);
    fclose(param);

    /* le a entrada */
    inst = fopen(argv[1], "r");
    fscanf(inst, "%d", &nJobs);
    jobs = (Job*)memAlloc(sizeof(Job) * nJobs);
    for (i = 0; i < nJobs; i++) {
        jobs[i].id = i;
        fscanf(inst, "%d %d", &jobs[i].task1, &jobs[i].task2);
    }
    fclose(inst);


    /* DEBUG: imprime a entrada */
    if (DEBUG) {
        fprintf(stderr, "entrada:\n");
        for (i = 0; i < nJobs; i++) {
            fprintf(stderr, "job%d: %d %d\n", jobs[i].id+1, jobs[i].task1, jobs[i].task2);
        }
        fprintf(stderr, "\n");
    }


    /* resolucao do FSP por BnB */
    solution = bnb(jobs, nJobs, maxExecTime, maxNodes);
    permSol = setPerm(solution->ndSol->sched, nJobs, nJobs);


    if (DEBUG) {
        fprintf(stderr, "++ melhor solucao encontrada: \n");
        printNode(solution->ndSol, nJobs);
    }

    /* imprime a saida */
    if (solution->nNodesChecked >= maxNodes) {
        printf("* execucao interrompida por limite de nos explorados\n");
    } else if (solution->timeElapsed >= maxExecTime) {
        printf("* execucao interrompida por limite de tempo\n");
    } else {
        printf("* execucao finalizada normalmente\n");
    }

    printf("* foram explorados %d nos em %d segundos\n",
            solution->nNodesChecked, solution->timeElapsed);

    printf("+ valor primal %d encontrado em %d segundos\n",
            solution->primalv, solution->primalt);
    printf("+ valor dual %d encontrado em %d segundos\n",
            solution->dualv, solution->dualt);

    printf("> melhor solucao encontrada: ");
    for (i = 0; i < nJobs; i++) {
        printf("%d ", permSol[i] + 1);
    }
    printf("(%d)\n", solution->ndSol->lowBound);


    /* libera a memoria */
    freeNode(solution->ndSol);
    free(solution);
    free(permSol);
    free(jobs);

    return EXIT_SUCCESS;
}

